package find.least.index.sum.of.two.array;

import java.util.Arrays;

/**
 * @Time 2019/12/20
 * @author 王光浩
 * @Need 给出两个数组，找出两个数组中都拥有且下标相加最小的元素值（如果有多个则全部返回）
 * @Thinking 暴力法。
 *           解法如下：使用双层循环，第一层循环遍历第一个数组，第二层循环遍历第二个数组，循环的主体在第二层循环中，
 *                    将第一个数组中的元素值和第二个数中所有元素值比，判断是否存在相同值，如果存在判断下标和是否大于
 *                    minimum值，如果大于，则继续下一个循环，如果等于，则将该下标对应的元素加入到result数组中，如果
 *                    小于，则将result数组清空，并且将该下标对应的元素加入到result数组中。
 *           复杂度分析：时间复杂度O（n^2*x），空间复杂度O（n*x）
 *           缺点：时间复杂度过高（为什么过高呢？对于第一个数组的每一个元素我们都需要遍历一次第二个数组）
 *           改进：在该题中我们需要从两个数组中找到元素值相同且下标和最小的元素值，所以我们可以使用HashMap来解决该问题
 *                 HashMap的key为元素值，vuale为每一个key对应的下标，这样可以先见第一个数组存入hashMap中，然后循环判断
 *                 第二个数组的元素是否存在于HashMap中，这样就完成了找出两个数组中值相同的元素，剩下的就是找出最小下标和对于
 *                 的元素了。
 */
public class MyMethodOne {
    public String[] findRestaurant(String[] list1, String[] list2) {
        int list1Len=list1.length;
        int list2Len=list2.length;
        String[] result=new String[list1Len>list2Len?list1Len:list2Len];     //保存最后结果
        int index=0;                                          //result下标
        int minimum=list1Len+list2Len;                        //最小下标和
        //双层循环，将最小下标和的数组元素值保存在result中
        for(int i=0;i<list1Len;i++) {
        	for(int j=0;j<list2Len;j++) {
        		if(list1[i].equals(list2[j]) && (i+j)<=minimum) {
        			//当前下标和小于minimum时将result结果清空，重置index的值
        			if(i+j<minimum) {    
        				index=0;
        				minimum=i+j;
        			}
        			result[index]=list2[j];
        			index++;
        		}
        	}
        }
        return Arrays.copyOf(result, index);                //将数组中多余的部分截去
    }
}
